\section{最大公因式}


\begin{frame}{最大公因式}
如果多项式 $\varphi$ 既是 $f$ 的因式， 又是 $g$ 的因式， 那么 $\varphi$ 就称为 $f$ 与 $g$ 的一个\emph{公因式}或\emph{公因子}。
在公因式中占有特殊重要地位的是最大公因式。

\pause
\begin{definition}%定义6 
  设 $f, g$ 是 $P[x]$ 中两个多项式。 $P[x]$ 中多项式 $d$ 称为 $f, g$的一个\emph{最大公因式}或\emph{最大公因子}，如果它满足下面两个条件：
\begin{enumerate}
  \item $d$ 是 $f, g$ 的公因式;
    \item $f, g$ 的公因式全是 $d$ 的因式。
\end{enumerate}
\end{definition}

\pause
例如， 对于任意多项式 $f, f$ 就是 $f$ 与 $0$ 的一个最大公因式。 特别地， 根据定义，两个零多项式的最大公因式就是 $0$.

\pause
有了以上的定义后，先来看看最大公因式存在时的唯一性。
由定义不难看出，如果 $d_{1}, d_{2}$ 是 $f$ 与 $g$ 的两个最大公因式， 
那么一定有 $d_{1} \mid d_{2}$ 与 $d_{2} \mid d_{1}$, 因此由整除的互伴性可知 $d_{1}=c d_{2}$, 对某个$c\in P^*$. 
这就是说，两个多项式的最大公因式在可以相差一个非零常数倍的意义下是唯一确定的。 

\pause
下面我们来解决最大公因式的存在性问题， 以下的证明也给出了一个具体求法。
最大公因式的存在性的证明主要根据带余除法，关于带余除法我们指出以下事实：
\end{frame}

\begin{frame}


\begin{lemma}%引理 
  \label{126}
如果有等式
\begin{equation*}
f=q g+r \tag{1}
\end{equation*}
成立， 那么 $f, g$ 和 $g, r$ 有相同的公因式。
特别地，
$f, g$ 和 $g, r$ 有相同的最大公因式。
\end{lemma}


\pause
\begin{proof}
如果 $\varphi\mid g, \varphi\mid  r$, 那么由 (1), $\varphi \mid f$. 这就是说， $g$,
$r$ 的公因式全是 $f, g$ 的公因式。 反过来， 如果 $\varphi\mid f, \varphi\mid  g$, 那么 $\varphi$ 一定整除它们的组合
$r=f-q g.$
这就是说， $\varphi$ 是 $g, r$ 的公因式。 由此可见， 如果 $g, r$ 有一个最大公因式 $d$, 那么 $d$ 也就是 $f, g$ 的一个最大公因式。 
\end{proof}

\pause
  \begin{theorem}%定理2 
    \label{0FD}
  对于 $P[x]$ 中任意两个多项式 $f, g$, 在 $P[x]$ 中存在一个最大公因式 $d$, 且 $d$ 可以表成 $f, g$ 的一个组合， 即有 $u, v\in P[x]$ 使
  \begin{equation*}
  d=u f+v g . \tag{2}
\end{equation*}
\end{theorem}

(2)称为 \emph{B\'ezout (贝祖) 等式}。
\end{frame}

\begin{frame}

\begin{proof}
如果 $f, g$ 有一个为零， 譬如说， $g=0$, 那么 $f$ 就是一个最大公因式，且
\[
f=1 \cdot f+1 \cdot 0 .
\]
\pause
下面来看一般的情形。 无妨设 $g \neq 0$. 按带余除法，用 $g$ 除 $f$, 得到商 $q_{1}$,余式 $r_{1}$; 如果 $r_{1} \neq 0$, 就再用 $r_{1}$ 除 $g$,得到商 $q_{2}$,余式 $r_{2}$; 又如果 $r_{2} \neq 0$, 就用 $r_{2}$ 除 $r_{1}$, 得出商 $q_{3}$,余式 $r_{3}$; 如此辗转相除下去，显然，所得余式的次数不断降低， 即
\[
\partial(g)>\partial\left(r_{1}\right)>\partial\left(r_{2}\right)>\cdots,
\]
因此在有限次之后，必然有余式为零。
\pause
于是我们有一串等式
\[
  \begin{aligned}
  f &= q_{1} g+r_{1}, \\
g &= q_{2} r_{1}+r_{2}, \\
& \cdots \cdots  \\
r_{i-2} &= q_{i} r_{i-1}+r_{i}, \\
& \cdots \cdots \\
r_{s-2} &= q_{s} r_{s-1}+r_{s}, \\
r_{s-1} &= q_{s+1} r_{s}+0 .
\end{aligned}
\]
\pause
$r_{s}$ 与 $0$ 的最大公因式是 $r_{s}$. 
根据前面的说明， $r_{s}$ 也就是 $r_{s}$ 与 $r_{s-1}$ 的一个最大公因式; 同样的理由， 逐步推上去， $r_{s}$ 就是 $f$ 与 $g$ 的一个最大公因式。
\end{proof}

\end{frame}


\begin{frame}

\begin{proof}[续]
由上面的倒数第二个等式，我们有
\[
r_{s}=r_{s-2}-q_{s} r_{s-1} .
\]
再由倒数第三式， $r_{s-1}=r_{s-3}-q_{s-1} r_{s-2}$, 代入上式可消去 $r_{s-1}$, 得到
\[
r_{s}=\left(1+q_{s} q_{s-1}\right) r_{s-2}-q_{s} r_{s-3} .
\]
然后根据同样的方法用它上面的等式逐个地消去 $r_{s-2}, \cdots, r_{1}$, 再并项就得到
\[
r_{s}=u f+v g,
\]
这就是定理中的 (2)式。 
\end{proof}
\pause
定理证明中用来求最大公因式的方法通常称为\emph{辗转相除法}。

\pause
我们知道，两个不全为零的多项式的最大公因式总是一个非零多项式。在这个情形，我们约定，用
\[
  (f, g)
\]
来表示首项系数是 $1$ 的那个最大公因式（称为\emph{首一最大公因式}）。
\pause
两个不全为零的多项式的首一最大公因式是唯一的。这样，若有等式$f=gq+r$ (其中$g\neq 0$), 则由
引理~\ref{126}~知
\[
(f,g)=(g,r).
\]
\end{frame}


\begin{frame}

\begin{example}%例 
设
\[
f=x^{4}+3 x^{3}-x^{2}-4 x-3, \quad g=3 x^{3}+10 x^{2}+2 x-3,
\]
求 $(f, g)$, 并求 $u, v$ 使
\[
(f, g)=u f+v g .
\]
\pause
辗转相除法可按下面的格式来做：
\setlength{\tabcolsep}{1pt}
\renewcommand{\arraystretch}{1.5}
\[
  \begin{tabular}{R|RRRR|RRRRR|L}
    q_2=-\frac{27}{5}x+9 & g=3x^3 & +10x^2 & +2x & -3 &f=  x^4 & +3x^3 & -x^2 & -4x & -3& q_1=\frac{1}{3}x-\frac{1}{9} \\
    & 3x^3 & +15x^2 & +18x && x^4 & +\frac{10}{3}x^3 & +\frac{2}{3}x^2 & -x & & \\
    \cline{2-10}
    &  & - 5x^2 & - 16x & - 3 &  & - \frac{1}{3}x^3 & - \frac{5}{3}x^2 & - 3x & - 3 & \\
    &  & - 5x^2 & - 25x & - 30 &  & - \frac{1}{3}x^3 & - \frac{10}{9}x^2 & - \frac{2}{9}x  & + \frac{1}{3} & \\
    \cline{2-10}
    & & r_2=& 9x & + 27 &  & r_1 = & -  \frac{5}{9} x^2 & - \frac{25}{9}x & - \frac{10}{3} & q_3 = -\frac{5}{81}x - \frac{10}{81} \\
    & & & & & & & - \frac{5}{9}x^2 & - \frac{5}{3}x && \\
    \cline{6-10}
     & & & & & & & & - \frac{10}{9}x  & - \frac{10}{3} & \\
     & & & & & & & & - \frac{10}{9}x  & - \frac{10}{3} & \\
    \cline{6-10}
    &&&&&&&&& 0 & 
  \end{tabular}
\]
用等式写出来， 就是
\end{example}
\end{frame}

\begin{frame}
\addtocounter{theorem}{-1}
\begin{example}[续]
\[
\begin{aligned}
f= q_1g+r_1, \quad
g= q_2r_1 + r_2, \quad
r_1= q_3r_2.
\end{aligned}
\]
\pause
因此
\[
  (f, g)=\frac{1}{9}r_2=x+3 .
\]
且
\[
\begin{aligned}
  (f,g) & = \frac{1}{9} r_2= \frac{1}{9}(g-q_2r_1)=\frac{1}{9}(g-q_2(f-q_1g))\\
  &=  \frac{1}{9}\left( -q_2f+(1+q_1q_2)g \right)=(-\frac{1}{9}q_2)f+(\frac{1}{9}(1+q_1q_2))g \\
& =\left(\frac{3}{5} x-1\right) f+\left(-\frac{1}{5} x^{2}+\frac{2}{5} x\right) g,
\end{aligned}
\]
\pause
于是， 令 $u=\frac{3}{5} x-1, v=-\frac{1}{5} x^{2}+\frac{2}{5} x$, 就有
\[
(f, g)=u f+v g .
\]
\end{example}
\pause
\begin{exercise}
  令$f=2 x^{4} - x^{3} - 4 x^{2} + 4 x - 1, g= 2 x^{3} - x^{2} + 2 x - 1$.
  求$(f,g)$并写出相应的B\'ezout等式。答案：$(f,g)=x - \frac{1}{2}$,
  B\'ezout等式为$uf+vg=(f,g)$, 其中$u=\frac{3}{20} x + \frac{1}{20}, 
  v=-\frac{3}{20} x^{2} - \frac{1}{20} x + \frac{9}{20}$.
\end{exercise}
\end{frame}

\begin{frame}
  \begin{definition}%定义7 
    $P[x]$ 中两个多项式 $f, g$ 称为\emph{互素} (也称互质) 的， 如果 $(f, g)=1$.
\end{definition}
\pause
例如，由$x^2+1=(x-1)(x+1)+2$知$(x^2+1, x-1)=(x-1,2)=1$, 故$x^2+1, x-1$互素。
\pause
显然， 如果两个多项式互素， 那么它们除去零次多项式外没有其他的公因式， 反之亦然。


\pause
\begin{theorem}%定理3 
  \label{11B}
$P[x]$ 中两个多项式 $f, g$ 互素的充分必要条件是有 $P[x]$ 中的多项式 $u, v$ 使
\[
u f+v g=1 .
\]
\end{theorem}

\pause
\begin{proof}
  必要性是定理~\ref{0FD}~的直接推论。
现在设有 $u, v$ 使
$u f+v g=1,$
而 $\varphi$ 是 $f$ 与 $g$ 的一个最大公因式。于是 $\varphi\mid f, \varphi\mid  g$, 从而 $\varphi \mid 1$,即 $f, g$ 互素。 
\end{proof}

\pause
由此可以证明

\begin{theorem}%定理4 
  \label{11C}
如果 $(f, g)=1$, 且 $f \mid g h$, 那么
$f \mid h$.
\end{theorem}
\end{frame}

\begin{frame}



\begin{proof}
由 $(f, g)=1$ 可知，有 $u, v$ 使
$u f+v g=1.$
等式两边乘 $h$,得
$u f h+v g h=h,$
因为 $f \mid g h$,所以 $f$ 整除等式左端， 从而
$f\mid h$.
\end{proof}

\pause
\begin{corollary}%推论 
如果 $f_{1}\mid g, f_{2}\mid g$, 且 $\left(f_{1}, f_{2}\right)=1$, 那么
$f_{1} f_{2} \mid g.$
\end{corollary}

\pause
\begin{proof}
由 $f_{1} \mid g$ 有
$g=f_{1} h_{1}$.
因为 $f_{2} \mid f_{1} h_{1}$, 且 $\left(f_{1}, f_{2}\right)=1$, 所以根据定理~\ref{11C}, 有 $f_{2} \mid h_{1}$, 即
$h_{1}=f_{2} h_{2},$
代入上式即得
$g=f_{1} f_{2} h_{2}$.
这就是说，
$f_{1} f_{2}\mid g$.
\end{proof}

\pause
我们指出
\begin{observation*}
首一最大公因式不随基域的扩大而改变。
\end{observation*}
\pause
\begin{proof}
事实上，考虑不全为零的$f, g\in P[x]$, $\bar{P}$是包含$P$的数域。
我们在$P[x]$中辗转相除得到了$f,g$在$P[x]$中最大公因式$r_s\in P[x]$,
由于带余除式不随基域的扩大而改变，
这个过程也是$\bar{P}[x]$中辗转相除的过程，因此$r_s$也是$f,g$在$\bar{P}[x]$中的最大公因子。
$r_s\in P[x]$表明$r_s$的首项系数$c$落在$P$中，因而无论是在$P[x]$中还是在$\bar{P}[x]$中都有$(f,g)=\frac{1}{c}r_s\in P[x]$.
\end{proof}
\end{frame}

\begin{frame}

在上面，最大公因式与互素的概念， 都是对两个多项式定义的。事实上，对于任意多个多项式 $f_{1}, f_{2}, \cdots, f_{s}$ ($s \geqslant 2$) 也同样可以定义最大公因式。
\begin{definition}
  $d$ 称为 $f_{1}, f_{2}, \cdots, f_{s}$ ($s \geqslant 2$) 的一个\emph{最大公因式}， 如果 $d$ 具有下面的性质：
\begin{enumerate}
\item $d \mid f_{i}, i=1,2, \cdots, s$;
    \item 如果 $\varphi \mid f_{i}, i=1,2, \cdots, s$, 那么 $\varphi \mid d$.
    \end{enumerate}
  \end{definition}

  \pause
显然一些零多项式有惟一的最大公因式：零多项式。
\pause
对不全为零的$f_1, f_2, \cdots, f_s$, 我们会在命题~\ref{147}~中建立和之前相似的结论，包括最大公因式的存在性、唯一性和B\'ezout等式。
\pause
我们仍用符号 $\left(f_{1}, f_{2}, \cdots, f_{s}\right)$ (或 $\gcd(f_1, \cdots, f_k)$) 来表示首一最大公因式。 
\pause
如果 $\left(f_{1}, f_{2}, \cdots, f_{s}\right)=1$, 那么 $f_{1}, f_{2}, \cdots, f_{s}$ 就称为\emph{互素}的。

\pause
\begin{proposition}
  \label{147}
  令 $f_1, f_2, \cdots, f_s\in P[x]$不全为$0$ ($s\geqslant 2$). 那么
\begin{enumerate}
  \item $f_1,\cdots,f_s$的最大公因式存在，且相差个常数倍是唯一的。
  \pause
\item 若$f_1, \cdots, f_{s-1}$不全为零，则$\left(f_{1}, f_{2}, \cdots, f_{s}\right)=\left(\left(f_{1}, f_{2}, \cdots, f_{s-1}\right), f_{s}\right).$
  \pause
\item 对任意的最大公因式$d$，存在$u_1, u_2, \cdots, u_s\in P[x]$使得
  \begin{equation}\tag{3}
    u_1f_1+u_2f_2+\cdots+u_sf_s=d\qquad(\text{B\'ezout等式}).
\end{equation}
\end{enumerate}
\end{proposition}


\end{frame}

\begin{frame}
  由上述命题(2)可知我们可以递归地求首一最大公因式，如
  \[
    \left( f_1,f_2,f_3,f_4 \right) = \left( (f_1,f_2,f_3),f_4 \right)=\left( ((f_1,f_2),f_3),f_4 \right) = ((f_1,f_2),f_3,f_4).
  \]

  \vspace{-.5em}
  \pause
  \begin{example} \label{146}
  \vspace{-1em}
  \[
  \begin{aligned}
      (x^2-1, x^3-1, x^4-1, x^5-1)&= (x^2-1,x^4-1, x^3-1,  x^5-1)\\
        &= (x^2-1, x^3-1, x^5-1)\\
        &=  (x-1,x^5-1)=x-1.
      \end{aligned}
\]
\end{example}
\pause
\begin{proof}
    我们对$s\geqslant 2$归纳来证明最大公因式存在。$s=2$的情形已知，假设$s>2$. 不妨设$f_1\neq 0$. 
    由归纳假设，$d'=(f_1, \cdots, f_{s-1})$存在. 
    令$\tilde{d}=(d', f_s)$. 显然$\tilde{d}\mid f_i$, 对所有$i$. 另一方面，若$h$为$f_1,f_2,\cdots,f_s$的公因式，
    则$h\mid d', h\mid f_s$, 从而$h\mid \tilde{d}$. 
    因此$\tilde{d}$为$f_1, f_2, \cdots, f_s$的最大公因式。唯一性由整除的互伴性易知。

    \pause
    我们同样对$s$归纳来证明B\'ezout等式存在。只用对$\tilde{d}$证明且只用考虑$s>2$. 
    由归纳假设，存在$w_1, \cdots, w_{s-1}, u, v\in P[x]$使得
  \[
      w_1f_1+\cdots+w_{s-1}f_{s-1}=d',\qquad ud'+vf_s=\tilde{d}.
  \]
  这样\[
      (uw_1)f_1+\cdots+(uw_{s-1})f_{s-1}+vf_s=\tilde{d}.
  \]
\end{proof}

\end{frame}


\begin{frame}{小结}
  \begin{enumerate}
    \item 何为几个多项式的最大公因式？
    \item 最大公因式的唯一性和存在性如何？
    \item 若何求两个不全为零的多项式的首一最大公因式？
      多个多项式呢？
    \item 何为B\'ezout等式？
    \item 何为互素？可如何判断？相关的结论有哪些？
    \item 系数域扩大时，首一最大公因子可会改变？为何？
  \end{enumerate}
\end{frame}
